#define MAXSIZE 10

typedef struct
{
    /* data */
    int val;
    // cur 保存指向下一个节点的索引
    int cur;
} compont, staticList[MAXSIZE];

// cur = 0 表示空指针
// 备用元素指未被使用的数组元素
// 对数组的第一个元素和最后一个元素作为特殊元素处理，不存储数据
// 第一个数组元素即下标为0的元素，用于存储备用链表的第一个元素的下标索引
// 最后一个数组元素即下标为MAXSIZE-1 的元素，用于存储第一个有数值的链表元素
int init(staticList list)
{
    for (int i = 0; i < MAXSIZE - 1; i++)
        list[i].cur = i + 1;
    list[MAXSIZE - 1].cur = 0; // 当前staticlist 为空
    return 1;
}

// 模拟malloc 函数
// 若备用链表非空，则返回备用链表的下标，否则返回0；
// 有值数组的cur 指向下一个有值数组元素下标，最后一个数组元素指向0
int Malloc_SLL(staticList list)
{
    int i = list[0].cur;
    if (list[0].cur)
        list[0].cur = list[i].cur; // 分配之后，头节点指向备用链表的下一个元素
    return i;
}

// 模拟free 函数
int Free_SLL(staticList list, int index)
{
    list[index].cur = list[0].cur;
    list[0].cur = index;
}

// 返回链表长度
int ListLength(staticList list)
{
    int node = list[0].cur;
    int length = 0;
    while (node != 0)
    {
        node = list[node].cur;
        length++;
    }
    return length;
}

// 静态链表下标从1开始
int ListInsert(staticList list, int index, int val)
{
    if (index < 1 || index > ListLength(list) + 1)
        return 0;

    int node = Malloc_SLL(list);
    if (!node)
        return 0;

    int next = list[MAXSIZE - 1].cur;
    list[node].val = val;
    for (int i = 0; i < index; i++)
    {
        next = list[next].cur;
    }
    list[node].cur = list[next].cur;
    list[next].cur = node;
    return 1;
}


// 删除某个结点
int ListDelete(staticList list, int index)
{
    int node = list[MAXSIZE - 1].cur;

    // node 指向 index 前一个结点
    for (int i = 1; i < index - 1; i++)
    {
        node = list[node].cur;
    }

    int next = list[node].cur;

    list[node].cur = list[next].cur;
    Free_SLL(list, node);
    return 1;
}
